home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / gnu / djgpp / src / libgplus.5 / libgplus / etc / adt-exam / keyhash.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-01-15  |  4.7 KB  |  166 lines

  1. // Date: Tue, 20 Sep 88 01:03:21 -0700
  2. // From: "Douglas C. Schmidt" <schmidt%crimee.ics.uci.edu@PARIS.ICS.UCI.EDU>
  3. // 
  4. // 
  5. // The following is an Obstack-based program, which outputs all the GCC
  6. // reserved words in an input file redirected from cin 
  7. // In addition, I found a neat use for
  8. // derived types by defining a word-by-word input class that is based
  9. // upon the class Obstack.  Finally, there is the added bonus of seeing
  10. // how the O (1) time GCC perfect hash function recognizer from GCC 1.35
  11. // works; I've incorporated the relevant code in this short routine.
  12. // Feel free to fold, spindle, or mutilate this code.
  13. // 
  14.  
  15. #include <stream.h>
  16. #include <ctype.h>
  17. #include <Obstack.h>
  18.  
  19. #define NIL(TYPE) ((TYPE *)0)
  20.  
  21. class Word_Read : private Obstack
  22. {
  23. public:
  24.   Obstack::free; // Allow the derived type to inherit only this member function.
  25.  
  26.   // Make the default something reasonable, like 80 columns.
  27.   Word_Read (int Default_Len = 80): Obstack(Default_Len)
  28.     {
  29.       ;
  30.     }
  31.  
  32.   // A very rudimentary method for carving out the next word
  33.   // from the input.  Ignores most error conditions.  All non-
  34.   // words are skipped entirely.  A word is defined as a
  35.   // letter, followed by a sequence of letters, digits, and/or
  36.   // underbars `_'.
  37.  
  38.   char *operator ()(int& Len)
  39.     {
  40.       char c;
  41.       
  42.       while (cin.get (c) && !(isalpha (c) || c == '_'))
  43.         ;
  44.       
  45.       do
  46.         Obstack::grow (c);
  47.       while (cin.get (c) && (isalnum (c) || c == '_'));
  48.  
  49.       Len = Obstack::size ();
  50.       return cin.good () ? (char *)Obstack::finish (0) : 0;
  51.     }
  52.   
  53.   // Make the destructor print out something useful, like
  54.   // output a diagnostic.
  55.  
  56.   ~Word_Read ()
  57.     {
  58.       cout << "chunk_size = " << Obstack::chunk_size () << "\n";
  59.       cout << "size = " << Obstack::size () << "\n";
  60.       cout << "room = " << Obstack::room () << "\n";
  61.     }
  62. };
  63.  
  64. // Provides a nice example of the perfect hash function used to recognize
  65. // GCC reserved words in O(1) steps.
  66.  
  67. const int    MIN_WORD_SIZE = 2;
  68. const int    MAX_WORD_SIZE = 12;
  69. const int    MIN_KEY_SIZE  = 4;
  70. const int    MAX_KEY_SIZE  = 64;
  71.   
  72. class Lookup_Table
  73. {
  74. private:
  75.   static int Hash_Table[];
  76.  
  77.   static char *Reswords[];
  78.  
  79.   // And here it is....  Very simple, guaranteed to work!
  80.  
  81.   int Hash (char *Str,int Len)
  82.     {
  83.       switch (Len) 
  84.         {
  85.         default:
  86.         case 3:
  87.           Len += Hash_Table[Str[2]];
  88.         case 2:
  89.         case 1:
  90.           return Len + Hash_Table[Str[0]];
  91.         }
  92.     }
  93.   
  94. public:
  95.   
  96.   // Carries out the O (1) lookup for GCC reserved words!
  97.   int  operator () (char *Str,int Len);
  98. };
  99.  
  100. Lookup_Table::operator () (char *Str,int Len)
  101. {
  102.   if (Len <= MAX_WORD_SIZE && Len >= MIN_WORD_SIZE)
  103.     {
  104.       register int Key = Hash (Str,Len);
  105.  
  106.       if (Key >= MIN_KEY_SIZE && Key <= MAX_KEY_SIZE) 
  107.     if (*Reswords[Key] == *Str && !strcmp (Reswords[Key] + 1,Str + 1)) 
  108.       return 1;
  109.     }
  110.   return 0;   
  111. }
  112.  
  113. int  Lookup_Table::Hash_Table[] = 
  114.     {
  115.       64,  64,  64,  64,  64,  64,  64,  64,  64,  64,
  116.       64,  64,  64,  64,  64,  64,  64,  64,  64,  64,
  117.       64,  64,  64,  64,  64,  64,  64,  64,  64,  64,
  118.       64,  64,  64,  64,  64,  64,  64,  64,  64,  64,
  119.       64,  64,  64,  64,  64,  64,  64,  64,  64,  64,
  120.       64,  64,  64,  64,  64,  64,  64,  64,  64,  64,
  121.       64,  64,  64,  64,  64,  64,  64,  64,  64,  64,
  122.       64,  64,  64,  64,  64,  64,  64,  64,  64,  64,
  123.       64,  64,  64,  64,  64,  64,  64,  64,  64,  64,
  124.       64,  64,  64,  64,  64,   1,  64,   9,  17,  15,
  125.       28,  19,  29,  15,  64,   2,  64,  64,  25,   4,
  126.       16,  22,  40,  64,  11,  23,   1,   1,  16,   2,
  127.       64,  64,   8,  64,  64,  64,  64,  64,
  128. };
  129.  
  130. char * Lookup_Table::Reswords[] =
  131. {
  132.       "", "", "", "", "if", "", "int", "", "union", "while", "__typeof", 
  133.       "__inline", "__typeof__", "__inline__", "auto", "__asm", "asm", "__asm__",
  134.       "return", "__alignof", "goto", "__alignof__", "void", "__const",
  135.       "enum", "__const__", "extern", "__volatile", "char", "__volatile__",
  136.       "do", "switch", "unsigned", "inline", "register", "double", "const",
  137.       "sizeof", "static", "continue", "struct", "break", "case", "for",
  138.       "signed", "long", "else", "typeof", "typedef", "volatile", "short",
  139.       "", "", "", "", "", "float", "", "", "", "", "", "", "", "default",
  140. };
  141.  
  142.  
  143. static void Store_Buf (char *Buf)
  144.   cout << "Storing reserved word " << Buf << "\n";
  145.   //  Just kidding!  But you get the idea....
  146. }
  147.  
  148. main (int argc, char *argv[])
  149. {
  150.   Word_Read    Get_Next_Word;
  151.   Lookup_Table Is_Reserved_Word;
  152.   char *Buf;
  153.   int   Len;
  154.   
  155.   while (Buf = Get_Next_Word (Len)) 
  156.     if (Is_Reserved_Word (Buf,Len)) 
  157.       Store_Buf (Buf);          // Keep reserved words
  158.     else                        
  159.       Get_Next_Word.free (Buf); // Discard non-reserved words
  160.   
  161.   return 0;
  162. }
  163.  
  164.  
  165.